Thomas Debris

INRIA Saclay, LIX

Introduction and research - Codes and Lattices: Real Twins or Distant Cousins?

Codes and lattices share many mathematical similarities; a code is defined as a subspace of a vector space over a finite field, and typically endowed with the Hamming metric, while a lattice is a discrete subgroup of an Euclidean vector space. Both objects have found over the last two decades similar applications in cryptography.
Code and lattice-based crypto-systems can be built relying either on the hardness of finding a close codeword or a close lattice point from a given target, a task called decoding. In both disciplines, a considerable amount of work has been made to study the decoding difficulty by identifying its sources of hardness (via reductions) and by designing algorithms to solve it (via cryptanalysis). However, despite many similarities, very few works brought closer codes and lattices in a cryptographic context by studying them in parallel via a common language.
The aim of this talk is to exhibit a dictionary between codes and lattices showing that techniques for studying the decoding difficulty turned out to be the same. We will mainly focus our attention on Fourier duality which is, as we will see, the crucial tool to obtain worst-to-average case reductions (classical or quantum) or to understand recent dual attacks for both codes and lattices.

Slides

Philippe Gaborit

XLIM, Université de Limoges

Introduction - Survey on Hamming based cryptography

Hamming based cryptography has been known for more than 45 years starting with the famous McEliece scheme, moreover the recent NIST standardization competition has been a true accelerator for the field, there are still three Hamming code-based scheme in the NIST competition (McEliece, BIKE and HQC). In this talk we will survey the complexity (both practical and theoretical) of difficult problems considered for Hamming based cryptography and we will also survey main encryption and signature schemes. We will see that over the time it is now possible to obtain very efficient and secure schemes (both in term of size of parameters and implementation).

Reseach - Recent advances in Rank based cryptography

Rank based cryptography was introduced in 1991 and can somehow be seen for Hamming based cryptography as the equivalent of elliptic curve cryptography for Discrete logarithm based cryptography. Problems are naturally more difficult and can naturally lead to smaller parameter sizes. In this talk we will review the difficulty of main problems in rank based cryptography and survey the main encryption and signature algorithms with the most recent advances. We will also present open problems.

Alice Pellet--Mary

Institut de mathématiques de Bordeaux, CNRS, INRIA Bordeaux

Introduction - How to build cryptography from lattices?

In this talk I will explain how to build encryption and signature schemes from the hardness of some lattice problems. I will focus particularly on the lattice isomorphism problem (LIP), and highlight its similarities with code problems.
I will also give a brief introduction to module lattices, which are lattices with an extra algebraic structure (they are small rank modules in some number field of large degree). These module lattices are heavily used for practical cryptographic schemes, due to the time and memory improvements they allow compared to plain lattices. But their extra structure might also help an attacker who would like to solve some algorithmic problem in these lattices (this will be continued in the research talk...)

Slides

Research - Algorithms for the module lattice isomorphism problem in certain fields

This talk will be devoted to a variant of the lattice isomorphism problem, which uses module lattices instead of plain lattices (named module-LIP). This problem is used by the signature scheme Hawk, which is the only lattice-based scheme selected at round 2 for the NIST call for additional signatures.
We will see that when the module has rank 2 and the field is a totally real number field, there exists an efficient polynomial time algorithm to solve the module-LIP problem. I will then briefly explain how well or bad this algorithm extends to other families of number fields, such as cyclotomic fields (the ones used in Hawk) or NTRUPrime fields.
This is based on joint works with Guilhem Mureau, Clémence Chevignard, Pierre-Alain Fouque, Georges Pliatsok, Alexandre Wallet and Wessel van Woerden.

Slides and Notes